package com.guqj.basis.datastruct.binarytree;

import java.util.Arrays;

/**
 * <p>
 * 堆是一颗完全二叉树。 完全二叉树有一个重要的特点，给定任意一个节点，可以根据其编号直接快速计算出其父节点和孩子节点编号。<br>
 * 如果编号为i，则父节点编号即为i/2，左孩子编号即为2*i,右孩子编号即为2*i+1。比如，对于5号节点，父节点为5/2即2，左孩子为2*5即10，
 * 右孩子为2*5+1即11<br>
 * 最大堆是指，每个节点都不大于其父节点,根节点就是所有节点中最大的<br>
 * 最小堆与最大堆正好相反，每个节点都不小于其父节点，根节点就是所有节点中最小的<br>
 * 查找和遍历就是对数组的查找和遍历，效率为O(N)
 * </p>
 * 
 * @author guqj
 * @date 2017年3月29日
 */
public class HeapSort {

	public static void heapSort(int[] array) {
		// 将待排序的序列构建成一个大顶堆
		for (int i = array.length / 2; i >= 0; i--) {
			heapAdjust(array, i, array.length);
		}

		// 逐步将每个最大值的根节点与末尾元素交换，并且再调整二叉树，使其成为大顶堆
		for (int i = array.length - 1; i > 0; i--) {
			swap(array, 0, i); // 将堆顶记录和当前未经排序子序列的最后一个记录交换
			heapAdjust(array, 0, i); // 交换之后，需要重新检查堆是否符合大顶堆，不符合则要调整
		}
	}

	/**
	 * 构建堆的过程 
	 * @param array 需要排序的数组
	 * @param index 需要构建堆的根节点的序号
	 * @param length 数组的长度
	 */
	private static void heapAdjust(int[] array, int index, int length) {
		int child = 0;
		int father = 0;
		for (father = array[index]; leftChild(index) < length; index = child) {
			child = leftChild(index);
			
			// 如果左子树小于右子树，则需要比较右子树和父节点
			if (child != length - 1 && array[child] < array[child + 1]) {
				child++; // 序号增1，指向右子树
			}

			// 如果父节点小于孩子结点，则需要交换
			if (father < array[child]) {
				array[index] = array[child];
			} else {
				break; // 大顶堆结构未被破坏，不需要调整
			}
		}
		array[index] = father;
	}

	// 获取到左孩子结点
	private static int leftChild(int i) {
		return 2 * i + 1;
	}

	// 交换元素位置
	private static void swap(int[] arr, int index1, int index2) {
		int tmp = arr[index1];
		arr[index1] = arr[index2];
		arr[index2] = tmp;
	}

	public static void main(String[] args) {
		int[] arr = { 50, 10, 90, 30, 70, 40, 80, 60, 20 };
		System.out.println("排序前：" + Arrays.toString(arr));
		heapSort(arr);
		System.out.println("排序后：" + Arrays.toString(arr));
	}
}
